package sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort_myselfTest {
    public static void main(String[] args) {
        int[] arr = new int[] {1,4,5,6,7,3,2,5,76,8,0,3,4,5,6,87,5,3,3};
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            /*
            Math.random()   [0, 1)
            Math.random() * (end - start)   [0, end - start)
            (int) (Math.random() * (end - start))   [0, end - start - 1]
            (int) (Math.random() * (end - start)) + start   [start, end - 1]
             */
            int index = (int) (Math.random() * (end - start)) + start;
            swap(arr, index, end);
            int[] p = partten(arr, start, end);
            quickSort(arr, start, p[0]);
            quickSort(arr, p[1], end);
        }
    }

    private static int[] partten(int[] arr, int start, int end) {
        int num = arr[end];
        int left = start - 1;
        int right = end;
        int index = start;
        while(index < right) {
            if (arr[index] < num) {
                swap(arr, ++left, index);
                index++;
            } else if (arr[index] > num) {
                swap(arr, --right, index);
            } else {
                index++;
            }
        }
        swap(arr, index, end);
        return new int[] {left, right + 1};
    }


    private static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
